package com.klun.project.common.constans.leetcode;


import com.klun.project.common.constans.entity.ListNode;
import com.klun.project.common.constans.utils.ParseUtils;

//编写一个函数，检查输入的链表是否是回文的。
// 示例 1：
// 输入： 1->2
//输出： false
//
// 示例 2：
// 输入： 1->2->2->1
//输出： true
//
// 进阶：
//你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
// Related Topics 栈 递归 链表 双指针
// 👍 124 👎 0

public class Solution0206 {

	public boolean isPalindrome(ListNode head) {
		if (head == null) return true;
		ListNode a = head;
		ListNode b = head.next;
		if (b == null) {
			return true;
		}
		ListNode c = head.next.next;
		if (c == null) return a.val == b.val;
		int count = 0;
		while (a != null) {
			count++;
			a = a.next;
		}
		a = head;
		a.next = null;
		boolean flag = false;
		while (c != null) {
			if (b.val == c.val && (count & 1) == 0) {
				b.next = c;
				c = c.next;
				flag = true;
				break;
			} else if (a.val == c.val && (count & 1) == 1) {
				b.next = c;
				flag = true;
				break;
			} else {
				b.next = a;
				a = b;
				b = c;
				c = c.next;
			}
		}
		if (!flag) return false;
		while (c != null && a != null) {
			if (c.val != a.val) {
				return false;
			}
			c = c.next;
			ListNode d = a.next;
			a.next = b;
			b = a;
			a = d;
		}
		return c == a;
	}

	public static void main(String[] args) {
		Solution0206 solution = new Solution0206();
		ListNode listNode = ParseUtils.ArrayToListNode("1,0,1,1");
		System.out.println(solution.isPalindrome(listNode));
	}


}
